In order to increase processing speed and throughput, it is common practice to utilize computer systems which have two or more independent central processing elements. Such systems are commonly used to construct large high-speed data processing systems and also to construct fault-tolerant systems which can continue to operate even in the event of circuit failures. Generally, in such systems other system resources, such as the memory elements and peripheral elements are shared by the multiple processing elements to reduce overall system costs.
In many single-processor and multi-processor systems, the processing elements are also multi-tasking in that several programs or tasks can be sequentially run on each processing element. The operating system software for many multi-tasking, multi-processor systems can execute on any of the processing elements in the system and may, in fact, execute on several processing elements at the same time. Since the operating system software typically allocates shared resources among the various system resources, a mechanism is needed to guarantee that the operating system software executing in several processing elements does not simultaneously attempt to use or modify the same shared resource from different processing elements.
An illustration of this problem is provided by a typical procedure by which the operating system running in a processing element in a multi-processor system selects a new task for the processing element to execute. Conventionally, this procedure begins by a processing element reading "queue pointer" information from a shared memory element. From the queue pointer information, the processing element determines the location in memory of the identity information for the highest-priority task waiting to be executed. After the task identity information has been read from memory, the task is selected by the processing element for execution. The processing element then changes the queue pointer information in the shared memory element to point to the location of the identity information of the next highest-priority task on the queue of tasks waiting to be executed.
A resource allocation problem occurs when several processing elements are carrying out this latter selection procedure at the same time and two or more processing elements attempt to read the same queue pointer information and select the same task for execution before any one of the processing elements has had a chance to change the pointer information to point to the next task on the queue. Although, in accordance with conventional memory construction, only one processing element can physically access a given memory element at any one time, a problem can still arise due to two interleaved accesses by different processing elements.
More specifically, each processing element typically executes a task by performing a predefined set of operations which set may involve two or more accesses to a memory element to obtain, modify and then store the modified information. If the stored information is modified during this sequence by another processing element, and the first processing element is not informed of the change, an error may result.
For example, in the previous illustration, during the task selection process, each processing element treats the initial read operation to obtain the queue pointer information and the subsequent write operation to modify the queue information as part of the same overall operation. Accordingly, the processing element does not expect the data in the memory element to be modified between the read and write operations. If another processing element accesses the memory between the read and write operations, a resource conflict results.
One prior art method of solving this resource allocation program is to constrain the operating system software to run on only one processing element. Such an approach, while effective in allocating resources presents problems for high-speed systems because the single-processor limitation becomes a bottleneck for the remainder of the system. In fault tolerant systems, a more serious problem is created if the processing element which is running the operating system fails.
Accordingly, it is an object of the invention to provide a computer resource allocation system which allocates resources among multiple processing elements in a multi-processor system.
It is another object of the present invention to provide a computer resource allocation system which allows each processing element in a multi-processor system to temporarily gain exclusive access to a particular shared resource.
It is still another object of the present invention to provide a computer resource allocation system which can be implemented using available shared memory resources.
It is yet another object of the present invention to provide a computer resource allocation system which can also insure equal utilization of multiple shared resources.
It is a further object of the present invention to provide a computer resource allocation system which can be used with many types of shared resources including memory and peripheral units.